1. Field of the Invention
The invention relates to Asynchronous Transfer Mode (ATM) telecommunications. More particularly, the invention relates to a method and apparatus which allows both shaped and unshaped virtual circuits (VCs) to be provisioned in a single virtual path (VP).
2. State of the Art
Perhaps the most awaited, and now fastest growing technology in the field of telecommunications is known as Asynchronous Transfer Mode (ATM) technology. ATM is providing a mechanism for removing performance limitations of local area networks (LANs) and wide area networks (WANS) and providing data transfers at a speed of on the order of gigabits/second. The variable length packets of LAN and WAN data are being replaced with ATM cells which are relatively short, fixed length packets. Because ATM cells can carry voice, video and data across a single backbone network, the ATM technology provides a unitary mechanism for high speed end-to-end telecommunications traffic.
Current ATM service is offered in different categories according to a user""s needs. Some of these categories include constant bit rate (CBR), variable bit rate (VBR), and unspecified bit rate (UBR). The CBR and VBR categories are subject to a contract where the network service provider guarantees a certain level of service. The UBR category is given the network service provider""s xe2x80x9cbest effortsxe2x80x9d after the CBR and VBR categories are serviced.
In an ATM network, an ATM cell is routed on the basis of VPI (virtual path identifier) and VCI (virtual channel identifier) values contained in the cell. On a particular virtual path (VP), defined by the value of the VPI field in the ATM cells on a particular physical link, there may be a number of virtual channels (VCs), each identified by a particular VCI value. As is well known, the VPI and VCI values are neither globally unique nor fixed; the values may change from node to node across a network.
In an ATM switch, traffic on each virtual channel is monitored and routed individually (different VCs on a common VP may, for example be routed differently within the switch). Incoming traffic is normally xe2x80x9cpolicedxe2x80x9d to ensure that the incoming traffic of individual VCs is conforming with its traffic contract, and the outgoing traffic is xe2x80x9cshapedxe2x80x9d to ensure that the outgoing traffic of individual VCs is conforming with its traffic contract (for example to alleviate any cell clumping that may have occurred in the switch), to reduce the risk of cells being discarded by a subsequent policing mechanism. Shaping is not performed on UBR connections.
In certain network configurations, an ATM switch may receive cells from multiple VCs all having a common VPI. Conversely, multiple VCs may be destined for transmission along a single VP over a common physical link. As mentioned above, each VC would conventionally be treated independently; this is required as each is required to meet its QoS (quality of service) objectives.
Prior art FIG. 1 illustrates portions of a state-of-the-art APEX E-Series ATM switch manufactured by General DataComm, Inc., Middlebury, Conn. The ATM switch includes one or more Line Interface Modules (LIMs) 10, each of which is associated with an E-Series Controller Card (ECC) 12, and one Switch Fabric Card 14 through which all of the ECCs are interconnected. On the ingress side of the LIM 10, the LIM deserializes the incoming bit stream and passes a parallel 16-bit cell stream over to the ECC 12. Each ATM cell has a fixed length of 53-bytes and its structure is dependent on the switch interface. The User-Network Interface (UNI) cell structure is used if the interface is between the user and the switch. The Network-Network Interface (NNI) cell structure is used if the interface is between switches.
Prior art FIGS. 2 and 3 illustrate the UNI and NNI cell structures respectively in a 16-bit parallel format. As mentioned above, the routing information for each cell is identified in the VPI and VCI fields. The PT (payload type) field indicates whether the cell contains user information or network management information. The CLP field indicates cell loss priority and the cell header can be checked against transmission errors using the HEC (header error check) field. In the UNI structure, the GFC (generic flow control) field is set to all zeros.
Returning now to prior art FIG. 1, the RCMP chipset 16 in the ECC 12 examines each ATM cell received from the LIM 10. If the connection specified in the cell header has not been provisioned, the cell is discarded. If the connection has been provisioned, and the xe2x80x9cpolicerxe2x80x9d has been enabled, the cell is policed according to the user""s contract. If the cell is not discarded, internal routing information provided by the VC record table 17 is appended to the cell header. According to the system used by the APEX Switch, three 16-bit words are appended to the beginning of the cell as illustrated in prior art FIG. 4 for the case of a UNI cell. The CELL ID field has two possible values: 00 for a user cell or host inserted cell and 11 for a backward reporting OAM (operations, administration, and maintenance) cell. The CL field is set to 1 to enable CLP marking. The MGT field is set to 1 to identify a management or extracted cell for the host. The CP field is set to one of four possible cell priority values: 00, 01, 10, 11, where 00 is the lowest priority. Switch Header 1 includes five fields: SCP, Link Dest, Spare, EFCI, and S. SCP is set to 1 for high priority (CP=10 or 11). Link Dest is a three bit address for indicating one of six links (000 through 101), for indicating a multicast cell (110), and for indicating a management cell (111). EFCI is set to 1 to enable EFCI (explicit forward congestion indication) marking. The S field is set to 1 for VPC (virtual path connection) flows and to 0 for VCC (virtual channel connection) flows.
With assistance from an ingress FPGA (field programmable gate array) 18, the RCMP 16 sends the cell with the appended internal routing information to the switch fabric card 14. Based on the internal routing information, the switch fabric card 14 routes the cell to the egress side of the desired slot (LIM and ECC pair). At the egress side of the ECC 12, the MAKER chipset 20, with the assistance of an egress FPGA 22 (and any buffering provided by buffers 24) receives the cell from the switch fabric card 14 and performs traffic shaping on shaped connections. Traffic shaping involves three stages: enqueueing, scheduling, and dequeueing.
Referring now to prior art FIG. 5, the enqueueing function involves setting up a separate dynamic buffer queue 32a-32n and 34a-34n for each provisioned VC where the buffer space is allocated according to Equation (1) where T(U) is the per VC queue allowed; Tf is the minimum buffer size set by management software; y is xe2x88x928 for CBR and rt-VBR, xe2x88x924 for nrt-VBR, and 0 for UBR; B is the total queue available (65535 for CBR, rt-VBR and UBR, 64511 for nrt-VBR); and U is the total queue usage.
T(U)=Tf+(2*exp(y)*(Bxe2x88x92U))xe2x80x83xe2x80x83(1)
The amount of per VC queue allowed is used to compare with the total number of enqueued cells via a cell counter (not shown). If the latter is less than the prior, then the cell is enqueued (to a location pointed by a link list free pointer). Otherwise, the cell is discarded.
The cells in each of the buffers 32a-32n are scheduled for dequeueing by a VC scheduler 36 which uses a continuous state leaky bucket algorithm from ITU-T I.371 to enforce cell emission rates from multiplexer 38. The leaky bucket algorithm is used to determine cell emission rates of shaped connections either at a peak shaping rate (PSR) or a sustained shaping rate (SSR). Cells are emitted at PSR if the current bucket level is less than or equal to a predetermined threshold. Otherwise, cells are emitted at SSR. The bucket level is updated after each cell is dequeued for emission and the emission time for the next cell is determined. Once the emission time of the next cell is determined, it is scheduled by pushing it onto a scheduling scoreboard where it awaits the emission opportunity.
The UBR cells in the buffers 34a-34n are dequeued according to a best efforts list 40 with fairness among UBR connection assured by a round robin selector 42 controlling multiplexer 44. As mentioned above, UBR connections do not have specified parameters and all the UBR connections in a link share whatever bandwidth is available after the shaped traffic is serviced. According to the best efforts list method, only one cell from each UBR can be present in the best efforts list at a time; and the cells are emitted on a first in first out basis.
As shown in FIG. 5 (in conjunction with FIG. 1), cells of both types (shaped and unshaped) are blended at multiplexer 46 for transmission to the ALM chipset (26 in FIG. 1, with connection table 28 providing translation). More particularly, a shaped cell is dequeued for emission when its scheduled time is equal to the current time. Unshaped cells are dequeued when there is available bandwidth, i.e. no shaped cell having the current time as its scheduled time. The ALM chipset (26 in FIG. 1) translates the internal VPI/VCI to the external VPI/VCI, removes the routing header and passes the cell in 16-bit streams to the LIM. The LIM serializes the 16-bit cell streams and passes the bit-stream out to the link.
The shaping methods described above are generally defined in ATM Forum Traffic Management 4.0. These methods work well, enforcing each VC contract, only if each VC is provisioned as an individual connection. If several VCs are provisioned to share a common VP tunnel, individual contracts cannot be enforced. When several VCs share the same VP, only the VP connection is provisioned and the VPI is used to identify which traffic streams are allowed to use this VP. This means that different traffic streams from multiple sources within the same VPI are all treated as the same source by the shaper since only one (VP) connection is provisioned. Therefore, per VC queuing, per contract shaping, and packet discard features can no longer be supported. Moreover, if unshaped (UBR) VCs are provisioned in the same VP, the VP contract may be violated because the aggregate of UBRs may utilize bandwidth beyond the bandwidth specified in the VP contract.
It is therefore an object of the invention to provide methods and apparatus for managing shaped and unshaped traffic in an ATM switch.
It is also an object of the invention to provide methods and apparatus for shaping multiple VCs within a single VP.
It is another object of the invention to provide methods and apparatus for managing multiple unshaped VCs within a single VP.
It is still another object of the invention to provide methods and apparatus for shaping multiple VCs and managing multiple unshaped VCs all within the same VP.
It is yet another object of the invention to provide methods and apparatus whereby, within a single VP, multiple shaped VCs emit cells according to their individual contracts and unshaped VCs emit cells based on available VP bandwidth and share the available bandwidth fairly.
In accord with these objects which will be discussed in detail below, the methods and apparatus of the present invention utilize two-stage shaping and two-priority queuing. According to the presently preferred embodiment, for each VP, a separate dynamic buffer is set up for each shaped VC and unshaped VC within the VP. The shaped cells stored in dynamic buffers are dequeued via VC scheduling (first stage shaper) to a high priority queue according to the shaped VC contracts, and the unshaped cells stored in dynamic buffers are dequeued in a round robin manner to a low priority queue. The outputs of both the high priority queue and the low priority queue are passed to a second stage shaper where cells from the high priority queue are scheduled according to the VP contract, and cells from the low priority queue are also scheduled according to the VP contract, but only when VP bandwidth is not being used by the high priority cells. In order to avoid overrunning the high priority queue in the second stage, the iPSR (Peak Shaping Rate increment) of the CBR VCs in the VP is chosen to be the iSSR (Sustained Shaping Rate increment) of the VP. The iPSR of the CBR VCs in the VP can be chosen to be higher than the iSSR of the VP as long as cell loss is not experienced at the second stage caused by overrunning the high priority queue. In addition, the calculated bucket for CBR service in the first stage is made a function of the Peak Cell Rate (PCR) of the VP. Otherwise, the enqueueing, dequeueing, and scheduling algorithms of the first and second stage shapers are the same.
The methods and apparatus of the invention can also be used with individually provisioned VCs in the following manner. Separate dynamic buffers are set up to store cells from each shaped VC outside of a shared VP and these cells are dequeued by the second stage shaper. Individual dynamic buffers are set up to store the cells from the UBR connections outside of a shared VP. These cells are dequeued to a best efforts list in a round robin manner when bandwidth is available. The outputs of the second stage shaper and the best efforts list are multiplexed and passed to the ALM chipset.
Additional objects and advantages of the invention will become apparent to those skilled in the art upon reference to the detailed description taken in conjunction with the provided figures.